10547. Истина, спрятанная в рекуррентности

 

Функция f определена следующим образом:

f(0, 0) = 1,

f(n, r) = , если n > 0 и 0 £ r £ n(k – 1) + 1,

f(n, r) = 0 иначе.

Вычислить значение x = mod m, где m = 10t.

Например, значения f(n, i) при k = 3 имеют вид (в пустых клетках стоят нули):

 

n \ i

0

1

2

3

4

5

6

7

8

0

1

 

 

 

 

 

 

 

 

1

1

1

1

 

 

 

 

 

 

2

1

2

3

2

1

 

 

 

 

3

1

3

6

7

6

3

1

 

 

4

1

4

10

16

19

16

10

4

1

 

Вход. На вход подается не более 1001 тестов. Каждая строка содержит три целых числа: k, n и t (0 < k, n < 1019, 0 < t < 10). Последний тест содержит k = n = t = 0 и не обрабатывается.

 

Выход. Для каждого теста вместе с его номером в отдельной строке вывести значение x.

 

Пример входа

1234 1234 4
2323 99999999999 8
4 99999 9
888 888 8
0 0 0

 

Пример выхода

Case #1: 736
Case #2: 39087387
Case #3: 494777344
Case #4: 91255296

 

 

РЕШЕНИЕ

рекуррентное соотношение

 

Анализ алгоритма

Рассмотрим все n - цифровые числа в системе исчисления с основанием k (включая числа с ведущими нулями). Общее их количество равно kn. Пусть f(n, r) – количество таких чисел, сумма цифр которых равна r. Тогда

f(n, r) = f(n – 1, r) + f(n – 1, r – 1) + … + f(n – 1, r – k + 1) = .

Минимальная сумма цифр для таких чисел равна 0, максимальная (k – 1) * n.  Просуммировав значения f(n, r) для r от 0 до (k – 1) * n, получим общее количество n - цифровых чисел в системе исчисления с основанием k, то есть kn.

Таким образом x = kn (mod 10t). Поскольку t < 10, то при вычислении модулярной экспоненты достаточно использовать 64-битный целочисленный тип.

 

Пример

Для первого теста имеет место равенство: 12341234 (mod 104) = 736.

 

Реализация алгоритма

При вычислении используем 64-битовый целый тип long long.

 

Функция вычисления kn mod m с оценкой сложности O(log2n):

 

long long powmod(long long x, long long y, long long n)

{

  long long res = 1;

  while(y > 0)

  {

    if (y & 1) res = (res * x) % n;

    y >>= 1;

    x = (x * x) % n;

  }

  return res;

}

 

Читаем входные значения k, n, t, вычисляем m = 10t. Находим x = kn (mod 10t) = (k mod m)n (mod 10t). Поскольку k < 1019, то во избежание переполнения перед вызовом функции powmod следует найти остаток от деления k на m. Таким образом значение первого аргумента k функции powmod будет не более 109 и при вычислении k * k не будет переполнения. Выводим результат с номером теста cs.

 

int cs = 1;

while(scanf("%lld %lld %lld",&k, &n, &t), k + n + t)

{

  m = 1; for(i = 0; i < t; i++) m *= 10;

  res = powmod(k % m,n,m);

  printf("Case #%d: %lld\n",cs++,res);

}